package a00_LeetCode.Tree.BST;

import a00_LeetCode.Tree.TreeNode;

/**
 * @Author quan
 * @Description 二叉搜索树与双向链表。
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * @Date 2023/4/5 16:57
 */
public class Num36_treeToDoublyList {
    /**
     * 传入一个以root为根的BST，就能将其转化为排序的双向链表，并返回转化后的链表头结点.
     * 其中链表prev 用 left代替
     * 链表 next 用 right代替
    */
    //----------------------测试一直不通过，剑指Offer36，奇了怪了-------------------
    public Node treeToDoublyList(Node root) {
        //base case
        if(root == null){
            return null;
        }
        //1、递归的遍历左树：先将左子树拉平转为双向链表
        Node head = treeToDoublyList(root.left);
        //先找到左半个链表的尾结点
        Node tail = head;
        //遍历
        while (tail != null){
            if(tail.right == null){
               //此时tail就是尾结点
                break;
            }
            tail = tail.right;
        }
        //2、此时tail走到了链表的尾部,将左半链表和根节点拼接：
        if(tail != null){
            tail.right = root;
            root.left = tail;
        }
        //3、再转换右子树
        Node right = treeToDoublyList(root.right);
        //拼接根节点和右半链表拼接
        if(right != null){
            right.left = root;
            root.right = right;
        }
        return head == null ? root : head;
    }
}
